#include "sort.h"

/*
 * (N^2)/2次比较和~N次交换
 * 1. 运行时间与输入无关，每次循环都扫描size-i个元素找出当前最小的元素放入位置i。
 * 2. 对比其他排序算法，选择排序移动的次数是最少的，每次循环最多交换两个元素。
 */
void selection(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int min = i;
        for (int j = i+1; j < size; j++) {
            if (arr[min] > arr[j])
                min = j;
        }
        if (min != i)
            swap(arr[min], arr[i]);
    }
}

/*
 * 平均情况下插入排序需要~N^2/4次比较以及~N^2/4次交换。
 * 最坏情况下需要~N^2/2 次比较和~N^2/2 次交换，
 * 最好情况下需要N-1次比较和0次交换。
 */
void insertion(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            swap(arr[j], arr[j-1]);
        }
    }
}

/*
 * 对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。
 * 改进版插入排序--希尔排序解决这个问题
 */
void shell(int arr[], int size) {
    int h = 0;
    while (h < size / 3) {
        h = 3 * h + 1;
    }

    while (h > 0) {
        for (int i = h; i < size; i++) {
            for (int j = i; j >= h && arr[j] < arr[j-h]; j-=h) {
                swap(arr[j], arr[j-h]);
            }
        }
        h = h / 3;
    }
}